package org.chengn.level_middle.context2477;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Title: Context2477
 * @Author ChengN
 * @Package org.chengn.level_middle.context2477
 * @Date 2023/12/5 1:33
 * @description: 力扣2477题 图论
 */
public class Context2477 {
    Map<Integer, List<Integer>> map = new HashMap<>();
    int seats = 0;
    long res = 0;
    public long minimumFuelCost(int[][] roads, int seats) {
        if (roads.length == 0) return 0;
        for (int[] road : roads) {
            List<Integer> node = map.getOrDefault(road[0], new ArrayList<>());
            node.add(road[1]);
            map.put(road[0], node);
            List<Integer> node2 = map.getOrDefault(road[1], new ArrayList<>());
            node2.add(road[0]);
            map.put(road[1], node2);
        }
        this.seats = seats;
        dfs(0, -1);
        return res;


    }

    public int dfs(int node, int lastNode) {
        List<Integer> road = map.get(node);
        if (road.size() == 1 && road.get(0) == lastNode) {
            return 0;
        }
        int thisRes = 0;
        for (int r : road) {
            if (r == lastNode) continue;
            long temp = dfs(r, node) + 1;
            res = res + (temp + seats - 1) / seats;
            thisRes += temp;
        }

        return thisRes;
    }
}
